procedure Legend.Generic_Search_Path (
   Map    : Region_Type; 
   From   : Point_Type;
   To     : Point_Type
   )
is
   subtype Axis_Type is Int16_t;

   subtype X_Axis is Axis_Type range Map.Top_Left.X .. Map.Bottom_Right.X;
   subtype Y_Axis is Axis_Type range Map.Top_Left.Y .. Map.Bottom_Right.Y;

   Visited : array(Y_Axis, X_Axis) of Axis_Type;

   -- first => nearast
   -- last  => fartest
   Stack : Point_Lists.List;

   function In_Map (P : Point_Type) return Boolean 
   is
   begin
      return P.X in X_Axis and P.Y in Y_Axis;
   end In_Map;

   function More_Near (P, Q : Point_Type) return Boolean
   is
      trip_p : Axis_Type := Visited(P.Y, P.X) + Distance(P, To);
      trip_q : Axis_Type := Visited(Q.Y, Q.X) + Distance(Q, To);
   begin
      return trip_p < trip_q;
   end More_Near;

   procedure Push (P : Point_Type)
   is
      i : Point_Lists.Cursor := Stack.First;
   begin
      while Point_Lists.Has_Element(i) loop
         declare
            Q : Point_Type := Point_Lists.Element(i);
         begin
            exit when More_Near(P, Q);
            Point_Lists.Next(i);
         end;
      end loop;
      Stack.Insert(i, P);
   end Push;

   function Pop return Point_Type
   is
      Result : Point_Type := Stack.First_Element;
   begin
      Stack.Delete_First;
      return Result;
   end Pop;

   procedure Generate_Result 
   is
      P : Point_Type := To;
      Q : Point_Type;
   begin
      Add_To_Path(To);
      loop
         for Face in Face_Type loop
            Q := P + Face_To_Offset(Face);
            if Q = From then
               return;
            end if;
            if In_Map(Q) then
               if Visited(Q.Y, Q.X) + 1 = Visited(P.Y, P.X) then
                  Add_To_Path(Q);
                  P := Q;
                  exit;
               end if;
            end if;
         end loop;
      end loop;
   end Generate_Result;

begin
   for y in Visited'Range(1) loop
      for x in Visited'Range(2) loop
         Visited(y, x) := (if Can_Reach((x, y)) then 0 else -1);
      end loop;
   end loop;

   Push(From);
   Visited(From.Y, From.X) := 1;
   while not Stack.Is_Empty loop
      declare
         P : Point_Type := Pop;
      begin
         for Face in Face_Type loop
            declare
               Q : Point_Type := P + Face_To_Offset(Face);
            begin
               if Q = To then
                  Visited(Q.Y, Q.X) := Visited(P.Y, P.X) + 1;
                  Generate_Result;
                  return;
               end if;
               if In_Map(Q) then
                  if Visited(Q.Y, Q.X) = 0 then
                     Visited(Q.Y, Q.X) := Visited(P.Y, P.X) + 1;
                     Push(Q);
                  end if;
               end if;
            end;
         end loop;
      end;
   end loop;
end Legend.Generic_Search_Path;


